//
// Created by daiyizheng on 2022/4/12.
//
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
    //sum - neg = target + neg
    // neg = (sum-target)/2
    //在数组 nums 列表中不可重复的选择数字组合，使得组合中所有数字之和为neg（背包容量）
    //求有多少组合数？
    // 0-1背包问题
    int findTargetSumWays(vector<int>& nums, int target) {
        int sum = 0;
        for (int& num : nums) {
            sum += num;
        }
        int diff = sum-target;
        if(diff%2==1 || diff<0)return 0;

        int n = nums.size(), neg = diff / 2;
        vector<vector<int>> dp(n + 1, vector<int>(neg + 1));
        dp[0][0] = 1;
        for (int i = 1; i <= n; i++) {
            int num = nums[i - 1];
            for (int j = 0; j <= neg; j++) {
                dp[i][j] = dp[i - 1][j];//不放
                if (j >= num) {//放
                    dp[i][j] += dp[i - 1][j - num];
                }
            }
        }
        return dp[n][neg];
    }
};